题解 CF1073F Choosing Two Paths

发表于 | 更新于

题目大意：有一棵树，从中选取$2$条链，其中任何一条链的端点不能被另一条链包含，求这两条链，使这两条链的公共的点的部分最长，若相同，使得总长度最长。

因为其中任何一条链的端点不能被另一条链包含，所以重合线段的两个端点的度一定$\geqslant3($两条链的端点在这个节点处分开),在一棵树上要求公共部分最长，有点像求树的直径的做法，两遍$dfs$，特殊的是在更新答案时只有这个点度$\geqslant3$时才更新。

这道题还有个要求，在求公共部分最长的情况下还要使总长度最长

那我们就在$u$和$v$的子树中，找离根最远和次远的点即可。

为了保证求出的两个端点的子树中，“离根最远和次远的点到根距离之和”是最长的，所以在dfs的时候若两个点距离根同样远，则根据它们“离根最远和次远的点到根距离之和”的大小来判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
struct node1{
    int to,dis,next;
}e[500000],e1[500000];
inline void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(int x) {write(x);puts("");}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int loc,ans,head[500000],head1[500000],dep[500000],ind[500000],f[500000],g[500000],cnt;
struct node{
    int x,sum;
    friend bool operator <(node y,node z){
        if (z.x!=y.x)return y.x<z.x;
        return y.sum<z.sum;
    }
}mx;
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;g[u]=f[u]=0;int cnt=0;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;++cnt;
        dfs(v,u);
        if (dep[f[v]]>dep[f[u]]){
            g[u]=f[u];
            f[u]=f[v];
        }else if (dep[f[v]]>dep[g[u]]){
            g[u]=f[v];
        }
    }
    if (!cnt)f[u]=u;
    if (cnt>1){
        node x={dep[u],dep[f[u]]+dep[g[u]]-dep[u]*2};
        if (mx<x){
            mx=x;
            loc=u;
        }
    }
}
int main(){
    int n=read();
    for (int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    mx={0,0};
    dfs(1,0);
    int a1=f[loc],b1=g[loc];
    mx={0,0};
    dfs(loc,0);
    int a2=f[loc],b2=g[loc];
    printf("%d %d\n%d %d\n",a1,a2,b1,b2);
    return 0;
}